# 杨辉三角(好题, 组合数的计算)
from leetcode import test_function as tf


def triangle(n):
    last_row = [1, 1]
    row_num = 2  # 遍历的三角的行号
    while True:  # 遍历每一行
        row = [1] * (row_num + 1)
        for i in range(row_num + 1):
            if i == 0 or i == row_num:  # 每行的首个和末尾元素为1, 不用改变
                continue
            row[i] = last_row[i - 1] + last_row[i]  # 每个元素等于上面两个元素之和
            if row[i] == n:
                return int((row_num + 1) * row_num / 2 + i + 1)
        last_row = row
        row_num += 1


def triangle_bi(n):
    """因为杨辉三角是一个对称的三角, 所以第一次出现的数字一定出现在三角的左半部分, 只需要考虑左半部分就可以"""
    last_row = [1, 1]
    row_num = 3  # 遍历的三角的行号, 从第3行开始遍历
    while True:  # 遍历每一行
        row = [1] * ((row_num + 1) >> 1)
        for i in range(len(row)):
            if i == 0:  # 每行的首个和末尾元素为1, 不用改变
                continue
            elif i == len(last_row):  # 最后一个元素
                row[i] = 2 * last_row[-1]
            else:  # 其他元素
                row[i] = last_row[i - 1] + last_row[i]  # 每个元素等于上面两个元素之和
            if row[i] == n:
                return int((row_num - 1) * row_num // 2 + i + 1)
        last_row = row
        row_num += 1


def triangle_opt(n):
    """杨辉三角有两个非常重要的特性:
    1. 每个数字是上一行两个数字之和
    2. 每一行也是一个组合数C(m, k) 即从m中选出k个的不同组合的个数
    例如:
    第3行 [1,3,3,1] = [C(0,3),C(1,3),C(2,3),C(3,3)]
    第4行 [1,4,6,4,1] = [C(0,4),C(1,4),C(2,4),C(3,4),C(4,4)]
    由于每一行都是一个对称的数组, 且左侧为递增序列, 因此可以直接使用二分法查找
    """

    if n == 1:
        return 1

    def combination(m, k, target):
        """计算组合数C(m, k)，从m中选取k个的不同的组合个数，并在计算过程中提前终止以优化性能。"""
        if k < 0 or k > m:
            return 0

        if k == 0 or k == m:
            return 1
        k = min(k, m - k)
        result = 1
        for i in range(1, k + 1):
            result = result * (m - k + i) // i
            if result > target:
                return result  # 提前终止，返回超过目标的值
        return result

    def find_m(n, k):
        """使用二分搜索找到满足C(m, k) = n的最小m。"""
        low = k
        high = 2 * n  # 扩大搜索范围以确保覆盖所有可能情况
        while low <= high:
            mid = (low + high) // 2
            c = combination(mid, k, n)
            if c < n:
                low = mid + 1
            elif c > n:
                high = mid - 1
            else:
                return mid
        return None

    min_pos = float('inf')
    max_k = int((2 * (n + 1)) ** 0.5) + 2  # 经验性设定k的最大值，覆盖更多可能性
    for k in range(1, max_k + 1):  # 其中k为行号
        m = find_m(n, k)  # m该数所在行的索引
        if m is not None:
            pos = m * (m + 1) // 2 + k + 1
            if pos < min_pos:
                min_pos = pos
    return min_pos if min_pos != float('inf') else -1


if __name__ == '__main__':
    inp = [{"n": 6}, {"n": 1000}, {"n": 10000}, {"n": int(1e9)}, ]
    out = [13, 500502, 50005002, 500000000500000002]
    # tf(triangle, inp, out)  # 仅计算10000以内的时间: 11.243052s
    # tf(triangle_bi, inp, out)  # 仅计算10000以内的时间: 6.408198
    tf(triangle_opt, inp, out)  # 仅计算10000以内的时间: 0.001008
